package com.javabasic.algorithm.leetcode;

/**
 * @author xiongmin
 * @version 0.0.1
 * @description Created by work on 2021/10/15 12:07 上午
 * @see
 */
public class MinStack {

    int[] arrayStack;
    int index;

    public MinStack() {
        arrayStack = new int[30000];
        index = 0;
    }

    public void push(int val) {
        arrayStack[index++] = val;
    }

    public void pop() {
        index--;
    }

    public int top() {
        return arrayStack[index-1];
    }

    public int getMin() {
        int minNumber = Integer.MAX_VALUE;
        for (int i = 0; i < index; i++) {
            if (arrayStack[i] < minNumber) {
                minNumber = arrayStack[i];
            }
        }
        return minNumber;
    }

}

/**
 * 解法二：空间换时间
 * 空间换时间，每次put元素的时候就计算出当前下标的最小值，获取最小值时就直接返回即可，不用从新计算
 */
class MinStack2 {

    int[] arrayStack;
    int index;
    int[] minArr;

    public MinStack2() {
        arrayStack = new int[30000];
        minArr = new int[30000];
        index = 0;
    }

    public void push(int val) {
        if (index == 0) {
            minArr[index] = val;
        } else {
            if (val < minArr[index-1]) {
                minArr[index] = val;
            } else {
                minArr[index] = minArr[index-1];
            }
        }
        arrayStack[index++] = val;

    }

    public void pop() {
        index--;
    }

    public int top() {
        return arrayStack[index-1];
    }

    public int getMin() {
        return minArr[index-1];
    }

}